package Tree;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @BelongsProject: SeniorArchitect-LeetCode
 * @BelongsPackage: Tree
 * @Author: zhuangxiaoyan
 * @CreateTime: 2023-10-26  08:52
 * @Description: TODO
 * @Version: 1.0
 */
public class 二叉树路径总和113 {

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> lists = new LinkedList<List<Integer>>();
        Deque<Integer> path = new LinkedList<Integer>();
        pathSum2(root, targetSum, path, lists);
        return lists;
    }

    private void pathSum2(TreeNode root, int targetSum, Deque<Integer> path, List<List<Integer>> lists) {
        if (root == null) {
            return;
        }
        // 向最后一个加入
        path.offerLast(root.val);
        targetSum -= root.val;
        // 三个值成立是才能算
        if (root.left == null && root.right == null && targetSum == 0) {
            lists.add(new LinkedList<Integer>(path));
        }
        // 递归
        pathSum2(root.left, targetSum, path, lists);
        pathSum2(root.right, targetSum, path, lists);
        // 回溯 删除最后一个
        path.pollLast();
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
